package com.cat.dataStructure;

/**
*   @description https://leetcode.cn/problems/minimum-add-to-make-parentheses-valid/description/?envType=problem-list-v2&envId=stack
*   @author 曲大人的喵
*   @create 2025/9/5 23:49
*   @since JDK17
*/

public class Solution56 {
    public int minAddToMakeValid(String s) {
        int ans = 0, n = s.length(), top = 0;
        for (int i = 0; i < n; i++) {
            if (s.charAt(i) == '(') {
                top++;
            } else {
                top--;
                ans += Math.max(-top, 0);
                top = Math.max(0, top);
            }
        }

        return ans + top;
    }
}
